home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / CBASE102.ARJ / NDOPS.C < prev    next >
Text File  |  1991-09-23  |  30KB  |  1,209 lines
  1. /*    Copyright (c) 1989 Citadel    */
  2. /*       All Rights Reserved        */
  3.  
  4. /* #ident    "@(#)ndops.c    1.5 - 91/09/23" */
  5.  
  6. #include <ansi.h>
  7.  
  8. /* ansi headers */
  9. #include <errno.h>
  10. #ifdef AC_STDLIB
  11. #include <stdlib.h>
  12. #endif
  13. #ifdef AC_STRING
  14. #include <string.h>
  15. #endif
  16.  
  17. /* non-ansi headers */
  18. #include <bool.h>
  19.  
  20. /* library headers */
  21. #include <blkio.h>
  22.  
  23. /* local headers */
  24. #include "btree_.h"
  25.  
  26. /*man---------------------------------------------------------------------------
  27. NAME
  28.      bt_ndalloc - allocate memory for node
  29.  
  30. SYNOPSIS
  31.      #include "btree_.h"
  32.  
  33.      btnode_t *bt_ndalloc(btp)
  34.      btree_t *btp;
  35.  
  36. DESCRIPTION
  37.      The bt_ndalloc function allocates an initialized in-core node for
  38.      btree btp.  The address of the node created is returned.
  39.  
  40.      bt_ndalloc will fail if one or more of the following is true:
  41.  
  42.      [EINVAL]       btp is not a valid btree pointer.
  43.      [ENOMEM]       Not enough memory is available for allocation by
  44.                     the calling process.
  45.      [BTENOPEN]     btp is not open.
  46.  
  47. SEE ALSO
  48.      bt_ndfree, bt_ndinit.
  49.  
  50. DIAGNOSTICS
  51.      On failure, a NULL pointer is returned, and errno set to indicate
  52.      the error.
  53.  
  54. ------------------------------------------------------------------------------*/
  55. #ifdef AC_PROTO
  56. btnode_t *bt_ndalloc(btree_t *btp)
  57. #else
  58. btnode_t *bt_ndalloc(btp)
  59. btree_t *btp;
  60. #endif
  61. {
  62.     btnode_t *btnp = NULL;
  63. #ifdef DEBUG
  64.     /* validate arguments */
  65.     if (!bt_valid(btp)) {
  66.         BTEPRINT;
  67.         errno = EINVAL;
  68.         return NULL;
  69.     }
  70.  
  71.     /* check if not open */
  72.     if (!(btp->flags & BTOPEN)) {
  73.         BTEPRINT;
  74.         errno = BTENOPEN;
  75.         return NULL;
  76.     }
  77. #endif
  78.     /* allocate storage for main node structure */
  79.     /* (calloc is used throughout to automatically set all bits 0) */
  80.     btnp = (btnode_t *)calloc((size_t)1, sizeof(btnode_t));
  81.     if (btnp == NULL) {
  82.         BTEPRINT;
  83.         errno = ENOMEM;
  84.         return NULL;
  85.     }
  86.     btnp->lsib = NIL;
  87.     btnp->rsib = NIL;
  88.     btnp->n = 0;
  89.     /* key array [1..m] (extra slot is for overflow) */
  90.     btnp->keyv = calloc((size_t)btp->bthdr.m, btp->bthdr.keysize);
  91.     if (btnp->keyv == NULL) {
  92.         BTEPRINT;
  93.         free(btnp);
  94.         errno = ENOMEM;
  95.         return NULL;
  96.     }
  97.     /* child node file postion array [0..m] */
  98.     btnp->childv = (bpos_t *)calloc((size_t)(btp->bthdr.m + 1), sizeof(*btnp->childv));
  99.     if (btnp->childv == NULL) {
  100.         BTEPRINT;
  101.         free(btnp->keyv);
  102.         free(btnp);
  103.         errno = ENOMEM;
  104.         return NULL;
  105.     }
  106.  
  107.     return btnp;
  108. }
  109.  
  110. /*man---------------------------------------------------------------------------
  111. NAME
  112.      bt_ndcopy - copy btree node
  113.  
  114. SYNOPSIS
  115.      #include "btree_.h"
  116.  
  117.      int bt_ndcopy(btp, tbtnp, sbtnp)
  118.      btree_t *btp;
  119.      btnode_t *tbtnp;
  120.      const btnode_t *sbtnp;
  121.  
  122. DESCRIPTION
  123.      The bt_ndcopy function makes an exact copy of the in-core node
  124.      pointed to by sbtnp to the in-core node pointed to by tbtnp.
  125.  
  126.      bt_ndcopy will fail if one or more of the following is true:
  127.  
  128.      [EINVAL]       btp is not a valid btree pointer.
  129.      [EINVAL]       tbtnp or sbtnp is the NULL pointer.
  130.  
  131. DIAGNOSTICS
  132.      Upon successful completion, a value of 0 is returned.  Otherwise,
  133.      a value of -1 is returned, and errno set to indicate the error.
  134.  
  135. ------------------------------------------------------------------------------*/
  136. #ifdef AC_PROTO
  137. int bt_ndcopy(btree_t *btp, btnode_t *tbtnp, const btnode_t *sbtnp)
  138. #else
  139. int bt_ndcopy(btp, tbtnp, sbtnp)
  140. btree_t *btp;
  141. btnode_t *tbtnp;
  142. const btnode_t *sbtnp;
  143. #endif
  144. {
  145. #ifdef DEBUG
  146.     /* validate arguments */
  147.     if (!bt_valid(btp) || tbtnp == NULL || sbtnp == NULL) {
  148.         BTEPRINT;
  149.         errno = EINVAL;
  150.         return -1;
  151.     }
  152. #endif
  153.     /* copy node sbtnp into tbtnp */
  154.     tbtnp->lsib = sbtnp->lsib;
  155.     tbtnp->rsib = sbtnp->rsib;
  156.     tbtnp->n = sbtnp->n;
  157.     memcpy(bt_kykeyp(btp, tbtnp, 1), bt_kykeyp(btp, sbtnp, 1), (size_t)(btp->bthdr.m * btp->bthdr.keysize));
  158.     memcpy(bt_kychildp(tbtnp, 0), bt_kychildp(sbtnp, 0), (size_t)((btp->bthdr.m + 1) * sizeof(*bt_kychildp(tbtnp, 0))));
  159.  
  160.     return 0;
  161. }
  162.  
  163. /*man---------------------------------------------------------------------------
  164. NAME
  165.      bt_nddelkey - delete key from btree node
  166.  
  167. SYNOPSIS
  168.      #include "btree_.h"
  169.  
  170.      int bt_nddelkey(btp, btnp, kn)
  171.      btree_t *btp;
  172.      btnode_t *btnp;
  173.      int kn;
  174.  
  175. DESCRIPTION
  176.      The bt_nddelkey function deletes the tuple kn from the in-core
  177.      node pointed to by btnp.
  178.  
  179.      bt_nddelkey will fail if one or more of the following is true:
  180.  
  181.      [EINVAL]       btp is not a valid btree pointer.
  182.      [EINVAL]       btnp is the NULL pointer.
  183.  
  184. SEE ALSO
  185.      bt_ndinskey, bt_ndsearch.
  186.  
  187. DIAGNOSTICS
  188.      Upon successful completion, a value of 0 is returned.  Otherwise,
  189.      a value of -1 is returned, and errno set to indicate the error.
  190.  
  191. ------------------------------------------------------------------------------*/
  192. #ifdef AC_PROTO
  193. int bt_nddelkey(btree_t *btp, btnode_t *btnp, int kn)
  194. #else
  195. int bt_nddelkey(btp, btnp, kn)
  196. btree_t *btp;
  197. btnode_t *btnp;
  198. int kn;
  199. #endif
  200. {
  201. #ifdef DEBUG
  202.     /* validate arguments */
  203.     if (!bt_valid(btp) || btnp == NULL) {
  204.         BTEPRINT;
  205.         errno = EINVAL;
  206.         return -1;
  207.     }
  208. #endif
  209.     /* delete key kn */
  210.     if (bt_kyshift(btp, btnp, kn + 1, -1) == -1) {
  211.         BTEPRINT;
  212.         return -1;
  213.     }
  214.  
  215.     return 0;
  216. }
  217.  
  218. /*man---------------------------------------------------------------------------
  219. NAME
  220.      bt_ndfree - free in-core node
  221.  
  222. SYNOPSIS
  223.      #include "btree_.h"
  224.  
  225.      void bt_ndfree(btnp)
  226.      btnode_t *btnp;
  227.  
  228. DESCRIPTION
  229.      The bt_ndfree function frees the in-core node pointed to by btnp.
  230.  
  231. SEE ALSO
  232.      bt_ndalloc.
  233.  
  234. ------------------------------------------------------------------------------*/
  235. #ifdef AC_PROTO
  236. void bt_ndfree(btnode_t *btnp)
  237. #else
  238. void bt_ndfree(btnp)
  239. btnode_t *btnp;
  240. #endif
  241. {
  242.     if (btnp == NULL) {
  243.         return;
  244.     }
  245.     if (btnp->keyv != NULL) free(btnp->keyv);
  246.     btnp->keyv = NULL;
  247.     if (btnp->childv != NULL) free(btnp->childv);
  248.     btnp->childv = NULL;
  249.     free(btnp);
  250.  
  251.     return;
  252. }
  253.  
  254. /*man---------------------------------------------------------------------------
  255. NAME
  256.      bt_ndfuse - btree node fuse
  257.  
  258. SYNOPSIS
  259.      #include "btree_.h"
  260.  
  261.      int bt_ndfuse(btp, lbtnp, rbtnp, pbtnp, pkn)
  262.      btree_t *btp;
  263.      btnode_t *lbtnp;
  264.      btnode_t *rbtnp;
  265.      btnode_t *pbtnp;
  266.      int pkn;
  267.  
  268. DESCRIPTION
  269.      The bt_ndfuse function fuses two nodes.  lbtnp and rbtnp point to
  270.      in-core copies of nodes to be fused, the left and right sibling,
  271.      respectively.  pbtnp points to an in-core copy of the parent
  272.      node.  pkn is the number of the key in pbtnp whose left child is
  273.      lbtnp and right child is rbtnp.
  274.  
  275.      On return, lbtnp contains the fused node and rbtnp is empty.
  276.      Both the left and right nodes are written to the file.  pbtnp is
  277.      modified during the fusion, but is not written to the file; the
  278.      calling program must write pbtnp to the file.
  279.  
  280.      bt_ndfuse will fail if one or more of the following is true:
  281.  
  282.      [EINVAL]       btp is not a valid btree pointer.
  283.      [EINVAL]       btnp, rbtnp, or pbtnp is NULL.
  284.      [EINVAL]       pkn is less than 1 or greater than pbtnp->n.
  285.      [BTENOPEN]     btp is not open.
  286.      [BTEPANIC]     The total number of keys in lbtnp and rbtnp is
  287.                     too large to fuse into one node.
  288.  
  289. SEE ALSO
  290.      bt_ndshift, bt_ndsplit.
  291.  
  292. DIAGNOSTICS
  293.      Upon successful completion, a value of 0 is returned.  Otherwise,
  294.      a value of -1 is returned, and errno set to indicate the error.
  295.  
  296. ------------------------------------------------------------------------------*/
  297. #ifdef AC_PROTO
  298. int bt_ndfuse(btree_t *btp, btnode_t *lbtnp, btnode_t *rbtnp, btnode_t *pbtnp, int pkn)
  299. #else
  300. int bt_ndfuse(btp, lbtnp, rbtnp, pbtnp, pkn)
  301. btree_t *btp;
  302. btnode_t *lbtnp;
  303. btnode_t *rbtnp;
  304. btnode_t *pbtnp;
  305. int pkn;
  306. #endif
  307. {
  308.     bttpl_t    bttpl;            /* (key, child address) tuple */
  309.     bool    leaf    = FALSE;    /* leaf node flag */
  310.     bpos_t    lnode    = 0;        /* left node block number */
  311.     bpos_t    rnode    = 0;        /* right node block number */
  312.  
  313.     /* initialize automatic aggregates */
  314.     memset(&bttpl, 0, sizeof(bttpl));
  315. #ifdef DEBUG
  316.     /* validate arguments */
  317.     if (!bt_valid(btp)) {
  318.         BTEPRINT;
  319.         errno = EINVAL;
  320.         return NULL;
  321.     }
  322.     if (lbtnp == NULL || rbtnp == NULL || pbtnp == NUL) {
  323.         BTEPRINT;
  324.         errno = EINVAL;
  325.         return -1;
  326.     }
  327.     if (pkn < 1 || pkn > pbtnp->n) {
  328.         BTEPRINT;
  329.         errno = EINVAL;
  330.         return -1;
  331.     }
  332.  
  333.     /* check if too many keys for fusion */
  334.     if (lbtnp->n + rbtnp->n > bt_ndmax(btp) - (leaf ? 0 : 1)) {
  335.         BTEPRINT;
  336.         errno = BTEPANIC;
  337.         return -1;
  338.     }
  339. #endif
  340.     /* check if leaf */
  341.     if (bt_ndleaf(lbtnp)) {
  342.         leaf = TRUE;
  343.     }
  344.  
  345.     /* get block number of sibling nodes */
  346.     lnode = rbtnp->lsib;
  347.     rnode = lbtnp->rsib;
  348.  
  349.     /* if internal node, bring down parent key pkn */
  350.     if (!leaf) {
  351.         bttpl.keyp = calloc((size_t)1, btp->bthdr.keysize);
  352.         if (bttpl.keyp == NULL) {
  353.             BTEPRINT;
  354.             errno = ENOMEM;
  355.             return -1;
  356.         }
  357.         if (bt_kyread(btp, pbtnp, pkn, &bttpl) == -1) {
  358.             BTEPRINT;
  359.             free(bttpl.keyp);
  360.             return -1;
  361.         }
  362.         bttpl.child = *bt_kychildp(rbtnp, 0);
  363.         if (bt_ndinskey(btp, lbtnp, lbtnp->n + 1, &bttpl) == -1) {
  364.             BTEPRINT;
  365.             free(bttpl.keyp);
  366.             return -1;
  367.         }
  368.         free(bttpl.keyp);
  369.         bttpl.keyp = NULL;
  370.     }
  371.  
  372.     /* move keys from rbtnp to lbtnp */
  373.     if (bt_kymvleft(btp, lbtnp, rbtnp, rbtnp->n) == -1) {
  374.         BTEPRINT;
  375.         return -1;
  376.     }
  377.  
  378.     /* return right node to free list */
  379.     if (bflpush(btp->bp, &rnode) == -1) {
  380.         BTEPRINT;
  381.         return -1;
  382.     }
  383.  
  384.     /* fix sibling links */        /*L=left N=new right */
  385.     lbtnp->rsib = rbtnp->rsib;    /* L -> N */
  386.     if (lbtnp->rsib == NIL) {    /* L <- N */
  387.         if (leaf) btp->bthdr.last = lnode;
  388.     } else {
  389.         if (bputbf(btp->bp, lbtnp->rsib, offsetof(btnode_t, lsib), &lnode, sizeof(lbtnp->lsib)) == -1) {
  390.             BTEPRINT;
  391.             return -1;
  392.         }
  393.     }
  394.  
  395.     /* initialize in-core copy of right sibling */
  396.     bt_ndinit(btp, rbtnp);
  397.  
  398.     /* delete parent key of right sibling */
  399.     if (bt_nddelkey(btp, pbtnp, pkn) == -1) {
  400.         BTEPRINT;
  401.         return -1;
  402.     }
  403.  
  404.     /* write fused node */
  405.     if (bt_ndput(btp, lnode, lbtnp) == -1) {
  406.         BTEPRINT;
  407.         return -1;
  408.     }
  409.  
  410.     return 0;
  411. }
  412.  
  413. /*man---------------------------------------------------------------------------
  414. NAME
  415.      bt_ndget - get btree node from file
  416.  
  417. SYNOPSIS
  418.      #include "btree_.h"
  419.  
  420.      int bt_ndget(btp, node, btnp)
  421.      btree_t *btp;
  422.      bpos_t node;
  423.      btnode_t *btnp;
  424.  
  425. DESCRIPTION
  426.      The bt_ndget function reads the contents of a node into the
  427.      in-core node pointed to by btnp to the file.  node is the block
  428.      number of the node in the file.
  429.  
  430.      bt_ndget will fail if one or more of the following is true:
  431.  
  432.      [EINVAL]       btp is not a valid btree pointer.
  433.      [EINVAL]       btnp is NULL.
  434.      [EINVAL]       node is NIL.
  435.      [EINVAL]       btnp is NULL.
  436.      [BTENOPEN]     btp is not open.
  437.  
  438. SEE ALSO
  439.      bt_ndput.
  440.  
  441. DIAGNOSTICS
  442.      Upon successful completion, a value of 0 is returned.  Otherwise,
  443.      a value of -1 is returned, and errno set to indicate the error.
  444.  
  445. ------------------------------------------------------------------------------*/
  446. #ifdef AC_PROTO
  447. int bt_ndget(btree_t *btp, bpos_t node, btnode_t *btnp)
  448. #else
  449. int bt_ndget(btp, node, btnp)
  450. btree_t *btp;
  451. bpos_t node;
  452. btnode_t *btnp;
  453. #endif
  454. {
  455.     void *buf = NULL;
  456. #ifdef DEBUG
  457.     /* validate arguments */
  458.     if (!bt_valid(btp) || node == NIL || btnp == NULL) {
  459.         BTEPRINT;
  460.         errno = EINVAL;
  461.         return -1;
  462.     }
  463.  
  464.     /* check if not open */
  465.     if (!(btp->flags & BTOPEN)) {
  466.         BTEPRINT;
  467.         errno = BTENOPEN;
  468.         return -1;
  469.     }
  470. #endif
  471.     /* read node from file */
  472.     buf = calloc((size_t)1, bt_blksize(btp));
  473.     if (buf == NULL) {
  474.         BTEPRINT;
  475.         errno = ENOMEM;
  476.         return -1;
  477.     }
  478.     if (bgetb(btp->bp, node, buf) == -1) {
  479.         BTEPRINT;
  480.         free(buf);
  481.         return -1;
  482.     }
  483.  
  484.     /* convert file node to in-core format */
  485.     memcpy(btnp, buf, offsetof(btnode_t, keyv));
  486.     memcpy(btnp->keyv,
  487.         ((char *)buf + offsetof(btnode_t, keyv)),
  488.         ((btp->bthdr.m - 1) * btp->bthdr.keysize));
  489.     memcpy(btnp->childv,
  490.         ((char *)buf + offsetof(btnode_t, keyv) +
  491.             ((btp->bthdr.m - 1) * btp->bthdr.keysize)),
  492.         (btp->bthdr.m * sizeof(*btnp->childv)));
  493.  
  494.     /* free buffer */
  495.     free(buf);
  496.  
  497.     return 0;
  498. }
  499.  
  500. /*man---------------------------------------------------------------------------
  501. NAME
  502.      bt_ndinit - initialize in-core node
  503.  
  504. SYNOPSIS
  505.      #include "btree_.h"
  506.  
  507.      void bt_ndinit(btp, btnp)
  508.      btree_t *btp;
  509.      btnode_t *btnp;
  510.  
  511. DESCRIPTION
  512.      The bt_ndinit function initializes the in-core node btnp.
  513.  
  514. ------------------------------------------------------------------------------*/
  515. #ifdef AC_PROTO
  516. void bt_ndinit(btree_t *btp, btnode_t *btnp)
  517. #else
  518. void bt_ndinit(btp, btnp)
  519. btree_t *btp;
  520. btnode_t *btnp;
  521. #endif
  522. {
  523. #ifdef DEBUG
  524.     /* validate arguments */
  525.     if (!bt_valid(btp) || btnp == NULL) {
  526.         BTEPRINT;
  527.         errno = EINVAL;
  528.         return;
  529.     }
  530. #endif
  531.     /* initialize btnp */
  532.     btnp->lsib = NIL;
  533.     btnp->rsib = NIL;
  534.     btnp->n = 0;
  535.     memset(btnp->keyv, 0, (size_t)(btp->bthdr.m * btp->bthdr.keysize));
  536.     memset(btnp->childv, 0, (size_t)((btp->bthdr.m + 1) * sizeof(*btnp->childv)));
  537.  
  538.     return;
  539. }
  540.  
  541. /*man---------------------------------------------------------------------------
  542. NAME
  543.      bt_ndinskey - insert key into btree node
  544.  
  545. SYNOPSIS
  546.      #include "btree_.h"
  547.  
  548.      int bt_ndinskey(btp, btnp, kn, bttplp)
  549.      btree_t *btp;
  550.      btnode_t *btnp;
  551.      int kn;
  552.      const bttpl_t *bttplp;
  553.  
  554. DESCRIPTION
  555.      The bt_ndinskey function inserts bttplp into the knth slot in
  556.      the in-core btree node btnp.  The node is not written to the
  557.      file.
  558.  
  559.      bt_ndinskey will fail if one or more of the following is true:
  560.  
  561.      [EINVAL]       btp is not a valid btree pointer.
  562.      [EINVAL]       btnp is the NULL pointer.
  563.      [EINVAL]       kn is less than 1 or greater than the number of
  564.                     keys in btnp plus 1.
  565.  
  566. SEE ALSO
  567.      bt_nddelkey, bt_ndsearch.
  568.  
  569. DIAGNOSTICS
  570.      Upon successful completion, a value of 0 is returned.  Otherwise,
  571.      a value of -1 is returned, and errno set to indicate the error.
  572.  
  573. ------------------------------------------------------------------------------*/
  574. #ifdef AC_PROTO
  575. int bt_ndinskey(btree_t *btp, btnode_t *btnp, int kn, const bttpl_t *bttplp)
  576. #else
  577. int bt_ndinskey(btp, btnp, kn, bttplp)
  578. btree_t *btp;
  579. btnode_t *btnp;
  580. int kn;
  581. const bttpl_t *bttplp;
  582. #endif
  583. {
  584. #ifdef DEBUG
  585.     /* validate arguments */
  586.     if (!bt_valid(btp) || btnp == NULL || bttplp == NULL) {
  587.         BTEPRINT;
  588.         errno = EINVAL;
  589.         return -1;
  590.     }
  591.     if (kn < 1 || kn > btnp->n + 1) {
  592.         BTEPRINT;
  593.         errno = EINVAL;
  594.         return -1;
  595.     }
  596.  
  597.     /* check if room to insert */
  598.     if (btnp->n >= btp->bthdr.m) {
  599.         BTEPRINT;
  600.         errno = BTEPANIC;
  601.         return -1;
  602.     }
  603. #endif
  604.     /* make an empty slot */
  605.     if (bt_kyshift(btp, btnp, kn, 1) == -1) {
  606.         BTEPRINT;
  607.         return -1;
  608.     }
  609.  
  610.     /* put new key into empty slot */
  611.     if (bt_kywrite(btp, btnp, kn, bttplp) == -1) {
  612.         BTEPRINT;
  613.         return -1;
  614.     }
  615.  
  616.     return 0;
  617. }
  618.  
  619. /*man---------------------------------------------------------------------------
  620. NAME
  621.      bt_ndleaf - is btree node leaf
  622.  
  623. SYNOPSIS
  624.      #include "btree_.h"
  625.  
  626.      int bt_ndleaf(btnp)
  627.      btnode_t *btnp;
  628.  
  629. DESCRIPTION
  630.      bt_ndleaf returns a true value if btnp is a leaf node or a false
  631.      value if it is not.  If btnp does not point to a valid in-core
  632.      btree node, the results are undefined.  bt_ndleaf is a macro.
  633.  
  634. SEE ALSO
  635.      bt_ndmax, bt_ndmin.
  636.  
  637. ------------------------------------------------------------------------------*/
  638. /* bt_ndleaf is defined in btree_.h. */
  639.  
  640. /*man---------------------------------------------------------------------------
  641. NAME
  642.      bt_ndmax - maximum keys per node
  643.  
  644. SYNOPSIS
  645.      #include "btree_.h"
  646.  
  647.      int bt_ndmax(btp)
  648.      btree_t *btp;
  649.  
  650. DESCRIPTION
  651.      bt_ndmin returns the maximum number of keys allowable in a node
  652.      of btree btp.  If btp does not point to a valid open btree, the
  653.      results are undefined.  bt_ndmax is a macro.
  654.  
  655. SEE ALSO
  656.      bt_ndleaf, bt_ndmin.
  657.  
  658. ------------------------------------------------------------------------------*/
  659. /* bt_ndmax is defined in btree_.h. */
  660.  
  661. /*man---------------------------------------------------------------------------
  662. NAME
  663.      bt_ndmin - minimum keys per node
  664.  
  665. SYNOPSIS
  666.      #include "btree_.h"
  667.  
  668.      int bt_ndmin(btp)
  669.      btree_t *btp;
  670.  
  671. DESCRIPTION
  672.      bt_ndmin returns the minimum number of keys allowable in a node
  673.      of btree btp.  If btp does not point to a valid open btree, the
  674.      results are undefined.  bt_ndmin is a macro.
  675.  
  676. SEE ALSO
  677.      bt_ndleaf, bt_ndmax.
  678.  
  679. ------------------------------------------------------------------------------*/
  680. /* bt_ndmin is defined in btree_.h. */
  681.  
  682. /*man---------------------------------------------------------------------------
  683. NAME
  684.      bt_ndput - put btree node to file
  685.  
  686. SYNOPSIS
  687.      #include "btree_.h"
  688.  
  689.      int bt_ndput(btp, node, btnp)
  690.      btree_t *btp;
  691.      bpos_t node;
  692.      const btnode_t *btnp;
  693.  
  694. DESCRIPTION
  695.      The bt_ndput function writes the contents of the in-core node
  696.      pointed to by btnp to the file.  node is the block number of the
  697.      node in the file.
  698.  
  699.      bt_ndput will fail if one or more of the following is true:
  700.  
  701.      [EINVAL]       btp is not a valid btree pointer.
  702.      [EINVAL]       btnp is NULL.
  703.      [EINVAL]       node is NIL.
  704.      [EINVAL]       btnp is NULL.
  705.      [BTENOPEN]     btp is not open.
  706.  
  707. SEE ALSO
  708.      bt_ndget.
  709.  
  710. DIAGNOSTICS
  711.      Upon successful completion, a value of 0 is returned.  Otherwise,
  712.      a value of -1 is returned, and errno set to indicate the error.
  713.  
  714. ------------------------------------------------------------------------------*/
  715. #ifdef AC_PROTO
  716. int bt_ndput(btree_t *btp, bpos_t node, const btnode_t *btnp)
  717. #else
  718. int bt_ndput(btp, node, btnp)
  719. btree_t *btp;
  720. bpos_t node;
  721. const btnode_t *btnp;
  722. #endif
  723. {
  724.     void *buf = NULL;
  725. #ifdef DEBUG
  726.     /* validate arguments */
  727.     if (!bt_valid(btp) || node == NIL || btnp == NULL) {
  728.         BTEPRINT;
  729.         errno = EINVAL;
  730.         return -1;
  731.     }
  732.  
  733.     /* check if not open */
  734.     if (!(btp->flags & BTOPEN)) {
  735.         BTEPRINT;
  736.         errno = BTENOPEN;
  737.         return -1;
  738.     }
  739. #endif
  740.     /* convert in-core node to file format */
  741.     buf = calloc((size_t)1, bt_blksize(btp));
  742.     if (buf == NULL) {
  743.         BTEPRINT;
  744.         errno = ENOMEM;
  745.         return -1;
  746.     }
  747.     memcpy(buf, btnp, offsetof(btnode_t, keyv));
  748.     memcpy(((char *)buf + offsetof(btnode_t, keyv)),
  749.         btnp->keyv,
  750.         ((btp->bthdr.m - 1) * btp->bthdr.keysize));
  751.     memcpy(((char *)buf + offsetof(btnode_t, keyv) +
  752.             ((btp->bthdr.m - 1) * btp->bthdr.keysize)),
  753.         btnp->childv,
  754.         (btp->bthdr.m * sizeof(*btnp->childv)));
  755.  
  756.     /* write node to file */
  757.     if (bputb(btp->bp, node, buf) == -1) {
  758.         BTEPRINT;
  759.         free(buf);
  760.         return -1;
  761.     }
  762.  
  763.     /* free buffer */
  764.     free(buf);
  765.  
  766.     return 0;
  767. }
  768.  
  769. /*man---------------------------------------------------------------------------
  770. NAME
  771.      bt_ndsearch - search btree node
  772.  
  773. SYNOPSIS
  774.      #include "btree_.h"
  775.  
  776.      int bt_ndsearch(btp, btnp, buf, knp)
  777.      btree_t *btp;
  778.      const btnode_t *btnp;
  779.      const void *buf;
  780.      int *knp;
  781.  
  782. DESCRIPTION
  783.      Function searches the in-core node btnp for the key pointed to by
  784.      buf.  On return, the location of the smallest key >= that pointed
  785.      to by buf is in the location pointed to by knp.
  786.  
  787.      bt_ndsearch will fail if one or more of the following is true:
  788.  
  789.      [EINVAL]       btp is not a valid btree pointer.
  790.      [EINVAL]       btnp is NULL.
  791.      [EINVAL]       buf is NULL.
  792.      [EINVAL]       knp is NULL.
  793.  
  794. SEE ALSO
  795.      bt_nddelkey, bt_ndinskey.
  796.  
  797. DIAGNOSTICS
  798.      Upon successful completion, a value of 0 is returned if the key
  799.      was found or a value of 1 is it was not found.  Otherwise, a
  800.      value of -1 is returned, and errno set to indicate the error.
  801.  
  802. ------------------------------------------------------------------------------*/
  803. #ifdef AC_PROTO
  804. int bt_ndsearch(btree_t *btp, const btnode_t *btnp, const void *buf, int *knp)
  805. #else
  806. int bt_ndsearch(btp, btnp, buf, knp)
  807. btree_t *btp;
  808. const btnode_t *btnp;
  809. const void *buf;
  810. int *knp;
  811. #endif
  812. {
  813.     int    cmp    = 0;        /* result of key comparison */
  814.     int    fld    = 0;        /* field number */
  815.     bool    found    = FALSE;    /* key found flag */
  816.     int    kn    = 0;        /* key number */
  817. #ifdef DEBUG
  818.     /* validate arguments */
  819.     if (!bt_valid(btp) || btnp == NULL || buf == NULL || knp == NULL) {
  820.         BTEPRINT;
  821.         errno = EINVAL;
  822.         return -1;
  823.     }
  824. #endif
  825.     /* initialize */
  826.     *knp = 0;
  827.  
  828.     /* locate key */
  829.     for (kn = 1; kn <= btnp->n; ++kn) {
  830.         for (fld = 0; fld < btp->fldc; ++fld) {
  831.             cmp = (*btp->fldv[fld].cmp)(bt_kykfp(btp, btnp, kn, fld),
  832.                     (char *)buf + btp->fldv[fld].offset,
  833.                     btp->fldv[fld].len);
  834.             if (cmp != 0) {
  835.                 break;
  836.             }
  837.         }
  838.         if (cmp == 0) {
  839.             found = TRUE;
  840.             break;
  841.         }
  842.         if (btp->fldv[fld].flags & BT_FDSC) {
  843.             if (cmp < 0) break;    /* descending order */
  844.         } else {
  845.             if (cmp > 0) break;    /* ascending order */
  846.         }
  847.     }
  848.     *knp = kn;
  849.  
  850.     return found ? 1 : 0;
  851. }
  852.  
  853. /*man---------------------------------------------------------------------------
  854. NAME
  855.      bt_ndshift - node shift
  856.  
  857. SYNOPSIS
  858.      #include "btree_.h"
  859.  
  860.      int bt_ndshift(btp, lbtnp, rbtnp, pbtnp, pkn, pnode)
  861.      btree_t *btp;
  862.      btnode_t *lbtnp;
  863.      btnode_t *rbtnp;
  864.      btnode_t *pbtnp;
  865.      int pkn;
  866.      bpos_t pnode;
  867.  
  868. DESCRIPTION
  869.      The bt_ndshift function shifts keys between two sibling nodes to
  870.      give them both the same number of keys (+/- 1).  lbtnp and rbtnp
  871.      are in-core copies of the two siblings.  pbtnp is an in-core copy
  872.      of the parent node of the two siblings.  pkn is the number of the
  873.      key in pbtnp whose left child is lbtnp and right child is rbtnp.
  874.  
  875.      The left, right, and parent nodes are written to the file.
  876.  
  877.      bt_ndshift will fail if one or more of the following is true:
  878.  
  879.      [EINVAL]       btp is not a valid btree pointer.
  880.      [EINVAL]       lbtnp, rbtnp, or pbtnp is NULL.
  881.      [EINVAL]       pkn is less than 1 or greater than pbtnp->n.
  882.      [BTENOPEN]     btp is not open.
  883.      [BTEPANIC]     Not enough keys in lbtnp and rbtnp to achieve
  884.                     the minimum number in both nodes.
  885.  
  886. SEE ALSO
  887.      bt_ndfuse, bt_ndsplit.
  888.  
  889. DIAGNOSTICS
  890.      Upon successful completion, a value of 0 is returned.  Otherwise,
  891.      a value of -1 is returned, and errno set to indicate the error.
  892.  
  893. ------------------------------------------------------------------------------*/
  894. #ifdef AC_PROTO
  895. int bt_ndshift(btree_t *btp, btnode_t *lbtnp, btnode_t *rbtnp, btnode_t *pbtnp, int pkn, bpos_t pnode)
  896. #else
  897. int bt_ndshift(btp, lbtnp, rbtnp, pbtnp, pkn, pnode)
  898. btree_t *btp;
  899. btnode_t *lbtnp;
  900. btnode_t *rbtnp;
  901. btnode_t *pbtnp;
  902. int pkn;
  903. bpos_t pnode;
  904. #endif
  905. {
  906.     bttpl_t    bttpl;            /* (key, child address) tuple */
  907.     bool    leaf    = FALSE;    /* leaf node flag */
  908.     bool    right    = FALSE;    /* shift direction flag */
  909.     int    ns    = 0;        /* number keys to shift */
  910.  
  911.     /* initialize automatic aggregates */
  912.     memset(&bttpl, 0, sizeof(bttpl));
  913. #ifdef DEBUG
  914.     /* validate arguments */
  915.     if (!bt_valid(btp)) {
  916.         BTEPRINT;
  917.         errno = EINVAL;
  918.         return NULL;
  919.     }
  920.     if (lbtnp == NULL || rbtnp == NULL || pbtnp == NULL) {
  921.         BTEPRINT;
  922.         errno = EINVAL;
  923.         return -1;
  924.     }
  925.     if (pkn < 1 || pkn > pbtnp->n) {
  926.         BTEPRINT;
  927.         errno = EINVAL;
  928.         return -1;
  929.     }
  930.  
  931.     /* check if not open */
  932.     if (!(btp->flags & BTOPEN)) {
  933.         BTEPRINT;
  934.         errno = BTENOPEN;
  935.         return NULL;
  936.     }
  937.  
  938.     /* check if enough keys to shift */
  939. if (lbtnp->n + rbtnp->n < 2 * bt_ndmin(btp)) {
  940.         errno = BTEPANIC;
  941.         return -1;
  942.     }
  943.  
  944.     /* check if too many keys to shift */
  945.     if (lbtnp->n + rbtnp->n > 2 * bt_ndmax(btp)) {
  946.         errno = BTEPANIC;
  947.         return -1;
  948.     }
  949. #endif
  950. /*printf("IN NDSHIFT: pkn = %d, pnode = %lu.\n", pkn, pnode);*/
  951.     /* set leaf and direction flags */
  952.     if (bt_ndleaf(lbtnp)) {
  953.         leaf = TRUE;
  954.     }
  955.     if (lbtnp->n > rbtnp->n) {
  956.         right = TRUE;
  957.     } else {
  958.         right = FALSE;
  959.     }
  960.  
  961.     /* if internal node, bring down parent key pkn */
  962.     if (!leaf) {
  963.         bttpl.keyp = calloc((size_t)1, btp->bthdr.keysize);
  964.         if (bttpl.keyp == NULL) {
  965.             BTEPRINT;
  966.             errno = ENOMEM;
  967.             return -1;
  968.         }
  969.         if (bt_kyread(btp, pbtnp, pkn, &bttpl) == -1) {
  970.             BTEPRINT;
  971.             free(bttpl.keyp);
  972.             return -1;
  973.         }
  974.         bttpl.child = *bt_kychildp(rbtnp, 0);
  975.         if (right) {
  976.             if (bt_ndinskey(btp, rbtnp, 1, &bttpl) == -1) {
  977.                 BTEPRINT;
  978.                 free(bttpl.keyp);
  979.                 return -1;
  980.             }
  981.             *bt_kychildp(rbtnp, 0) = *bt_kychildp(lbtnp, lbtnp->n);
  982.         } else {
  983.             if (bt_ndinskey(btp, lbtnp, lbtnp->n + 1, &bttpl) == -1) {
  984.                 BTEPRINT;
  985.                 free(bttpl.keyp);
  986.                 return -1;
  987.             }
  988.             *bt_kychildp(lbtnp, lbtnp->n) = *bt_kychildp(rbtnp, 0);
  989.         }
  990.         free(bttpl.keyp);
  991.         bttpl.keyp = NULL;
  992.     }
  993.  
  994.     /* calculate number of keys to shift (+ -> shift to right) */
  995.     ns = (lbtnp->n - rbtnp->n) / 2;
  996.     if (ns < 0) ns = -ns;
  997.  
  998.     /* shift keys */
  999.     if (right) {
  1000.         if (bt_kymvright(btp, lbtnp, rbtnp, ns) == -1) {
  1001.             BTEPRINT;
  1002.             return -1;
  1003.         }
  1004.     } else {
  1005.         if (bt_kymvleft(btp, lbtnp, rbtnp, ns) == -1) {
  1006.             BTEPRINT;
  1007.             return -1;
  1008.         }
  1009.     }
  1010.  
  1011.     /* bring up new parent key (child of pkn remains right node) */
  1012.     if (!leaf) {
  1013.         if (lbtnp->n > rbtnp->n) {
  1014.             memcpy(bt_kykeyp(btp, pbtnp, pkn), bt_kykeyp(btp, lbtnp, lbtnp->n), btp->bthdr.keysize);
  1015.             if (bt_nddelkey(btp, lbtnp, lbtnp->n) == -1) {
  1016.                 BTEPRINT;
  1017.                 return -1;
  1018.             }
  1019.         } else {
  1020.             memcpy(bt_kykeyp(btp, pbtnp, pkn), bt_kykeyp(btp, rbtnp, 1), btp->bthdr.keysize);
  1021.             *bt_kychildp(rbtnp, 0) = *bt_kychildp(rbtnp, 1);
  1022.             if (bt_nddelkey(btp, rbtnp, 1) == -1) {
  1023.                 BTEPRINT;
  1024.                 return -1;
  1025.             }
  1026.         }
  1027.     } else {
  1028.         memcpy(bt_kykeyp(btp, pbtnp, pkn), bt_kykeyp(btp, rbtnp, 1), btp->bthdr.keysize);
  1029.     }
  1030.  
  1031.     /* write lbtnp, rbtnp, and pbtnp to file */
  1032.     if (bt_ndput(btp, *bt_kychildp(pbtnp, pkn - 1), lbtnp) == -1) {
  1033.         BTEPRINT;
  1034.         return -1;
  1035.     }
  1036.     if (bt_ndput(btp, *bt_kychildp(pbtnp, pkn), rbtnp) == -1) {
  1037.         BTEPRINT;
  1038.         return -1;
  1039.     }
  1040.     if (bt_ndput(btp, pnode, pbtnp) == -1) {
  1041.         BTEPRINT;
  1042.         return -1;
  1043.     }
  1044.  
  1045.     return 0;
  1046. }
  1047.  
  1048. /*man---------------------------------------------------------------------------
  1049. NAME
  1050.      bt_ndsplit - btree node split
  1051.  
  1052. SYNOPSIS
  1053.      #include "btree_.h"
  1054.  
  1055.      int bt_ndsplit(btp, node, btnp, rbtnp, bttplp)
  1056.      btree_t *btp;
  1057.      bpos_t node;
  1058.      btnode_t *btnp;
  1059.      btnode_t *rbtnp;
  1060.      bttpl_t *bttplp;
  1061.  
  1062. DESCRIPTION
  1063.      The bt_ndsplit function splits a btree node.  btnp points to an
  1064.      in-core copy of the node to be split.  node is the block number
  1065.      of this node in the file.  The splitting will produce a new right
  1066.      sibling for this node.  Both the modified and the new node are
  1067.      written to the file.  If btnp had a right sibling prior to the
  1068.      split, the lsib link field in that node is updated, also.
  1069.  
  1070.      On return, btnp and rbtnp contain copies of the split node and
  1071.      its new right sibling, respectively, and the tuple pointed to by
  1072.      bttplp contains the (key, child address) tuple to be inserted in
  1073.      the parent of the split node; bttplp->child contains the block
  1074.      number of the new right sibling node.
  1075.  
  1076.      bt_ndsplit will fail if one or more of the following is true:
  1077.  
  1078.      [EINVAL]       btp is not a valid btree pointer.
  1079.      [EINVAL]       btnp, rbtnp, or bttplp is NULL.
  1080.      [BTENOPEN]     btp is not open.
  1081.      [BTEPANIC]     The number of keys in btnp is not equal to m.
  1082.  
  1083. SEE ALSO
  1084.      bt_ndfuse, bt_ndshift.
  1085.  
  1086. DIAGNOSTICS
  1087.      Upon successful completion, a value of 0 is returned.  Otherwise,
  1088.      a value of -1 is returned, and errno set to indicate the error.
  1089.  
  1090. ------------------------------------------------------------------------------*/
  1091. #ifdef AC_PROTO
  1092. int bt_ndsplit(btree_t *btp, bpos_t node, btnode_t *btnp, btnode_t *rbtnp, bttpl_t *bttplp)
  1093. #else
  1094. int bt_ndsplit(btp, node, btnp, rbtnp, bttplp)
  1095. btree_t *btp;
  1096. bpos_t node;
  1097. btnode_t *btnp;
  1098. btnode_t *rbtnp;
  1099. bttpl_t *bttplp;
  1100. #endif
  1101. {
  1102.     bool    leaf    = FALSE;    /* leaf node flag */
  1103.     int    midkn    = 0;        /* middle key number */
  1104.     bpos_t    rnode    = 0;        /* right node block number */
  1105.     int    terrno    = 0;        /* tmp errno */
  1106. #ifdef DEBUG
  1107.     /* validate arguments */
  1108.     if (!bt_valid(btp)) {
  1109.         BTEPRINT;
  1110.         errno = EINVAL;
  1111.         return NULL;
  1112.     }
  1113.     if (btnp == NULL || rbtnp == NULL || bttplp == NULL) {
  1114.         BTEPRINT;
  1115.         errno = EINVAL;
  1116.         return -1;
  1117.     }
  1118.  
  1119.     /* check if not open */
  1120.     if (!(btp->flags & BTOPEN)) {
  1121.         BTEPRINT;
  1122.         errno = BTENOPEN;
  1123.         return NULL;
  1124.     }
  1125.  
  1126.     /* check if node not one over full */
  1127.     if (btnp->n != bt_ndmax(btp) + 1) {
  1128.         BTEPRINT;
  1129.         errno = BTEPANIC;
  1130.         return -1;
  1131.     }
  1132. #endif
  1133.     /* initialize */
  1134.     bt_ndinit(btp, rbtnp);
  1135.  
  1136.     /* check if leaf node */
  1137.     if (bt_ndleaf(btnp)) {
  1138.         leaf = TRUE;
  1139.     }
  1140.  
  1141.     /* get new block for right sibling node */
  1142.     if (bflpop(btp->bp, &rnode) == -1) {
  1143.         BTEPRINT;
  1144.         return -1;
  1145.     }
  1146.  
  1147.     /* fix sibling links */        /*L=left R=right O=old right */
  1148.     rbtnp->rsib = btnp->rsib;    /* L    R -> O */
  1149.     btnp->rsib = rnode;        /* L -> R    O */
  1150.     rbtnp->lsib = node;        /* L <- R    O */
  1151.     if (rbtnp->rsib == NIL) {    /* L    R <- O */
  1152.         if (leaf) btp->bthdr.last = rnode;
  1153.     } else {
  1154.         if (bputbf(btp->bp, rbtnp->rsib, offsetof(btnode_t, lsib),
  1155.                     &rnode, sizeof(rbtnp->lsib)) == -1) {
  1156.             BTEPRINT;
  1157.             terrno = errno;
  1158.             bflpush(btp->bp, &rnode);
  1159.             errno = terrno;
  1160.             return -1;
  1161.         }
  1162.     }
  1163.  
  1164.     /* calculate middle key number */
  1165.     midkn = btnp->n / 2 + 1;
  1166.  
  1167.     /* get middle (key, child) tuple into bttplp */
  1168.     if (bt_kyread(btp, btnp, midkn, bttplp) == -1) {
  1169.         BTEPRINT;
  1170.         terrno = errno;
  1171.         bflpush(btp->bp, &rnode);
  1172.         errno = terrno;
  1173.         return -1;
  1174.     }
  1175.     bttplp->child = rnode;
  1176.  
  1177.     /* shift keys from left sibling */
  1178.     if (leaf) {
  1179.         /* move midkn thru n to right sibling */
  1180.         if (bt_kymvright(btp, btnp, rbtnp, btnp->n - midkn + 1) == -1) {
  1181.             BTEPRINT;
  1182.             return -1;
  1183.         }
  1184.     } else {
  1185.         /* move midkn + 1 thru n to right sibling */
  1186.         if (bt_kymvright(btp, btnp, rbtnp, btnp->n - midkn) == -1) {
  1187.             BTEPRINT;
  1188.             return -1;
  1189.         }
  1190.         /* delete midkn */
  1191.         if (bt_nddelkey(btp, btnp, midkn) == -1) {
  1192.             BTEPRINT;
  1193.             return -1;
  1194.         }
  1195.     }
  1196.  
  1197.     /* write split nodes */
  1198.     if (bt_ndput(btp, node, btnp) == -1) {
  1199.         BTEPRINT;
  1200.         return -1;
  1201.     }
  1202.     if (bt_ndput(btp, rnode, rbtnp) == -1) {
  1203.         BTEPRINT;
  1204.         return -1;
  1205.     }
  1206.  
  1207.     return 0;
  1208. }
  1209.